package demo8;

import lombok.Data;
import lombok.Setter;

import java.util.Collections;
import java.util.HashSet;

/**
 * >F:/integration/basic/SpringWithGradle-gitee/gradlew.bat --tests "demo8.EightQueenProblemTest.test1" :simple-demo:test --info -Dorg.gradle.jvmargs="-Xmx3g -Xms1g -verbose:gc"
 */
@Setter
public class EightQueenProblem {
    int n = 4;

    public EightQueenProblemImprove createEightQueenProblemImprove() {
        return new EightQueenProblemImprove();
    }

    @Setter
    public class EightQueenProblemImprove {
        int n;

        @Data
        class Result {
            private Integer[] integers;
        }

        /**
         * todo 有定式的，不要自己再造坏轮子了，没什么用的， 明天重新来
         * <p>
         * when n=8 ,
         * f(0,0)+f(1,2)
         * f(0,0)+f(1,4)
         * f(0,0)+f(1,5)
         * f(0,1)+f(6,3)
         * <p>
         * f(0)=0
         */
        public void makeUpTableStart() {
            // also print it ,
            Integer[] integers = new Integer[8];
            // inter

            integers[0] = new Integer(0);
            for (int i = 0; i <n; i++) {
                makeUpTable(-1, i, integers);
            }

        }

        private boolean ensureIfQualified(Integer[] integers, int row, int column1) {
            // rows between  equals column between
// 0-6
            for (int i = 0; i <= row; i++) {
                if (column1 - integers[i] == 0) {
                    return false;
                }
                int columnDiff = Math.abs(column1 - integers[i]);
                int rowDiff = row - (i-1) ;
                if (columnDiff == rowDiff) {
                    return false;
                }

            }

            return true;
        }

        /**
         * if(row==n-1){ // row =3 don't iterate. and print it ,
         * print(integers);
         * return;
         * }
         */
        // row from 0~7     -1~6
        public void makeUpTable(int row, int column1, Integer[] integers) {
            if (row == -1) {
            } else {
                int column2 = integers[row];
                boolean qualified = ensureIfQualified(integers, row, column1);
                //  need compare column1 with   all ele in the integers
                // how to ensure integers contains the duplicate data,
                if (!qualified) {
                    return;
                } else {
                    // print it when row ==n-1
                    if (row == n - 2) {
                        integers[row + 1] = column1;
                        print(integers);
                        return;
                    }
                }
            }


            for (int i = 0; i < n; i++) {
                // 1,0 1,1  1,2  1,3...
                // 2,0 2,1  2,2  2,3
                // 0,0 0,1 0,2 ..  还是没有避开重复和对角线queen面对面的问题啊！ 其实两个问题有相似点，》
                // 所以对角线问题: row必须按顺序进行递归的
                // only clone once , in the first level,
                if (row == -1) {
                    integers = integers.clone();
                }
                integers[row + 1] = column1;
                if (i != column1) {

                    makeUpTable(row + 1, i, integers);
                }

            }
            return;

        }

        private void print(Integer[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + ",");
            }
            System.out.println();
        }

        private void print(Integer[][] arr) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[i].length; j++) {
                    System.out.print(arr[i][j] + ",");
                }
            }
            System.out.println();
        }


    }

    /**
     * todo 有定式的，不要自己再造坏轮子了，没什么用的， 明天重新来
     * <p>
     * when n=8 ,
     * {{1,2,3,4,5,6,7,8},{1,2}},
     * need to supply the position of queen using the point   for every row and every column ,
     * like eight queen point ,
     */
    public void makeUpTableStart() {
        // also print it ,
        Integer[][] ints = new Integer[n][2];
        ints[0] = new Integer[]{0, 0};
        makeUpTable(ints, 0);

    }

    private void print(Integer[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + ",");
            }
        }
        System.out.println();
    }

    /**
     * x begin from 1, and y from 1  end to 8
     * when first pos is (1,1) ,the next pos could be
     * when  (x,y)=(1,1)
     * next: x=2~8
     * y=2~8
     * when  (x,y)=(2,3)
     * next: x=3~8
     * y=1+4~8
     * index from 0 to 8 ; times=8;
     */
    public void makeUpTable(Integer[][] ints, int index) {
        //  int[][] point={{1,1},{2,2}} + {3,3};
        if (index == n - 1) {
            print(ints);
            return;
        }
// need use the 制表法,
//        Integer[] xarrays = computeRemainAviabbleXAxis(ints, index);
        Integer[] yarrays = computeRemainAviabbleYAxis(ints, index);
        // get the lastest   pos. and to remove symmetrical pos,
        Integer[][] xyarrays = combinate(index, yarrays);
        Integer[] destpos = ints[index];
        // for loop
        for (int i = 0; i < xyarrays.length; i++) {

            if (xyarrays[i][0] == destpos[0] + 1 && destpos[1] + 1 == xyarrays[i][1] ||
                    xyarrays[i][0] == destpos[0] + 1 && destpos[1] - 1 == xyarrays[i][1] ||
                    xyarrays[i][0] == destpos[0] - 1 && destpos[1] + 1 == xyarrays[i][1] ||
                    xyarrays[i][0] == destpos[0] - 1 && destpos[1] - 1 == xyarrays[i][1]) {
                continue;
            }
            Integer[][] destarray = ints.clone();
            destarray[index + 1] = xyarrays[i];
            makeUpTable(destarray, index + 1);

        }

        return;
    }

    /**
     * 0,0
     * 1,1
     * -1,-1
     * -1,1
     * 1,-1
     */
    private Integer[][] combinate(Integer index, Integer[] yarrays) {
        int k = 0;
        // 1,1 1,2 1,3
        Integer[][] integers = new Integer[yarrays.length][2];
        for (int j = 0; j < yarrays.length; j++) {

            integers[k++] = new Integer[]{index, yarrays[j]};
        }
        return integers;

    }

    private Integer[] computeRemainAviabbleYAxis(Integer[][] ints, int index) {
        HashSet<Integer> set = new HashSet<Integer>();
        Collections.addAll(set, init);

        for (int i = 0; i <= index; i++) {
            int x = ints[i][1];
            set.remove(x);
        }

        Integer[] integers = set.toArray(new Integer[]{0});
        return integers;
    }

    Integer[] init = new Integer[]{0, 1, 2, 3};

    private Integer[] computeRemainAviabbleXAxis(Integer[][] ints, int index) {

        HashSet<Integer> set = new HashSet<Integer>();
        Collections.addAll(set, init);

        for (int i = 0; i <= index; i++) {
            int x = ints[i][0];
            set.remove(x);
        }

        Integer[] integers = set.toArray(new Integer[]{0});
        return integers;

    }

}
